package com.love.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {


    public static void main(String[] args) {

        int[] arr = {3,5,2,7,6,4,1};

        mergeSort(arr);

        System.out.println(Arrays.toString(arr));



    }


    public static void mergeSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }

        process(arr,0,arr.length - 1);

    }



    public static void process(int[] arr,int L,int R){
        // 1）important,这里要把他细分到最小单位，就是单个数，base case 要看递归的函数的参数（最好看中间体的参数 3）和 4））
        // 3）和 4）是左闭右开，细分到 最小单位 L == mid , mid + 1 = R, 也就是base case 的 L = R
        if(L == R){
            return;
        }
        // 2）中位数
        int mid = L + ((R - L) >>> 1);

        process(arr,L,mid);  // 3）

        process(arr,mid + 1,R); // 4）
        // 3）和 4）左闭右开


        merge(arr,L,mid,R);


    }

    public static void merge(int arr[],int L, int mid, int R){
        // R - L + 1 : 要以整个数组的 角度去看，虽然这个过程也是拆分到最小单位去 merge 的，但是不好想
        int[] help = new int[R - L + 1];
        int p1 = L;
        int p2 = mid + 1;
        int i = 0;

        // 注意：这里是 merge 过程，也就是说 L ... mid 和 mid + 1 这段是已经排好序的

        // 就分为 3 种情况 :
        // ① p1，p2 都没出界
        // ② p1 出界，p2 没出界，p2继续走完
        // ③ p2 出界，p1 没出界，p1继续走完
        // p1 和 p2 都出界，以己经比较完了
        while (p1 <= mid && p2 <= R){
            help[i++] = arr[p1] >= arr[p2] ? arr[p1++] : arr[p2++];
        }

        // 和下面循环，只会走一个
        while (p1 <= mid){
            help[i++] = arr[p1++];
        }

        while (p2 <= R){
            help[i++] = arr[p2++];
        }

        for ( i = 0; i < help.length ; i++) {
            arr[L + i] = help[i];
        }

    }





}
